#include <queue>
#include <stdio.h>
#include <string>
#include <vector>
#include <iostream>
#include <sys/time.h>
#include <unistd.h>
#include "HM_Queue.h"

void radixSort(std::vector<int>& vec, int d);


unsigned long GetLocalTimeMSec()
{
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec * 1000 + tv.tv_usec;
}

void GenRandomList(std::vector<int>& iVector)
{
    int seed = 1;
    for (int i=0; i<10; i++)
    {
        int ele = (seed * GetLocalTimeMSec()) % 100;
        iVector.push_back(ele);
        if (ele == 0)
        {
            seed = GetLocalTimeMSec();
        }
        else
        {
            seed = ele;
        }
        usleep(9*99);
    }
}

/**
 * @brief 基数排序
 * 
 * @param vec 
 * @param d 
 */
#ifndef _HM_QUEUE_H_
void radixSort(std::vector<int>& vec, int d)
{
    std::queue<int> digitQueue[10];
    int power = 1;

    auto collect = [&](){
        int i = 0;
        for (size_t digit = 0; digit < 10; digit++)
        {
            while (!digitQueue[digit].empty())
            {
                vec[i] = digitQueue[digit].front();
                digitQueue[digit].pop();
                i++;
            }
        }
    };

    auto distribute = [&](){
        for (size_t i = 0; i < vec.size(); i++)
        {
            digitQueue[(vec[i]/power)%10].push(vec[i]);
        }
    };

    for (size_t i = 0; i < d; i++)
    {
        distribute();
        collect();
        power *= 10;
    }
}

#else
void radixSort(std::vector<int>& vec, int d)
{
    // std::queue<int> digitQueue[10];
    HM_Queue<int> digitQueue[10];
    int power = 1;

    auto collect = [&](){
        int i = 0;
        for (size_t digit = 0; digit < 10; digit++)
        {
            while (!digitQueue[digit].empty())
            {
                vec[i] = digitQueue[digit].front();
                digitQueue[digit].pop();
                i++;
            }
        }
    };

    auto distribute = [&](){
        for (size_t i = 0; i < vec.size(); i++)
        {
            digitQueue[(vec[i]/power)%10].push(vec[i]);
        }
    };

    for (size_t i = 0; i < d; i++)
    {
        distribute();
        collect();
        power *= 10;
    }
}
#endif

int main()
{
    std::vector<int> vec;
    GenRandomList(vec);

    auto displayVec = [&](){
        for (auto &i : vec)
        {
            std::cout<<i<<" ";
        }
        std::cout<<std::endl;
    };

    displayVec();
    radixSort(vec, 2);
    displayVec();

    return 0;
}